Java Collections

在JDK1.2之前，代替着如今Java集合的工作类分别是：Dictionary， Vector，Stack和Properties，但因它们缺乏核心的、统一功能，造就了JDK1.2的新集合类：Collection（用于存储元素集合）和Map（用于存储键/值对映射 ）。

如今设计集合框架必须要满足以下几个目标：

• 该框架必须满足高性能，其底层的集合实现也必须是高效的，如：动态数组，链表，树和哈希表。
• 该框架必须允许不同类型的集合，以类似的方式进行工作，具有高度的互操作性。
• 对一个集合的扩展和适应必须是简单的。

依照上述标准，在开发过程中也可依据自身需求自定义集合对象。

图源：runoob.com

---

1. 集合框架体系

2. 各集合类差异

ArrayList、Vector、LinkedList对比

类型/属性	ArrayList	Vector	LinkedList
是否有序	排列有序，可重复	排列有序，可重复	排列有序，可重复
底层	数组	数组	双向循环链表
操作特性	查询快，增删慢	查询快，增删慢	查询慢，增删快
线程是否安全	线程不安全	线程安全	线程不安全
默认初始容量	10	10
扩容机制	容量不足时，一般扩容为原容量的1.5倍	容量不足时，一般扩容为原容量

LinkedList底层为是一个双向循环链表，没有初始化大小，因为链表为动态扩容，所以无需关心其容量大小，因此无扩容机制。

HashSet、TreeSet、LinkedHashSet对比

类型/属性	HashSet	TreeSet	LinkedHashSet
是否有序	排列无序，不可重复，可存在一个null	排列无序，不可重复，不可为null	排列有序，不可重复，可存在一个null
底层	哈希表	二叉树	哈希表存储，双向链表记录插入顺序
操作特性	存取速度快	排列存储
内部	HashMap	TreeMap + SortedSet	LinkedHashMap
默认初始容量	16
扩容机制	当达到阈值时，扩容为原容量的2倍

HashMap、HashTable、TreeMap对比

类型/属性	HashMap	HashTable	TreeMap
键值	键不可重复，值可重复	键不可重复，值可重复	键不可重复，值可重复
底层	哈希表	哈希表	二叉树
线程是否安全	线程不安全	线程安全
Key/Value	Key、Value都可为null	Key、Value都不可为null
默认初始容量	16	11

3. List

实现List接口的集合主要有：ArrayList，LinkedList，Vector。它们都可以容纳所有类型的对象，包括null值，允许重复，并且保证元素的存储顺序（可重复，顺序存储）。

0x1. ArrayList

ArrayList对数组进行了封装，实现了一套可变长度的数组操作，称之为动态数组，和普通的数组相同，采用了内存空间连续存储的方式，其优点是，遍历访问且随机访问元素的效率速度快，但是相应的缺点是增删将导致大量元素移动，所以增删速度慢。

0x2. Vector

Vector与ArrayList基本相同，唯一不同的是，Vector加入了线程锁。即同一时刻中，只能有一条线程操作该集合对象，而实现线程同步也导致了它的效率相对于ArrayList来说较低，在多线程操作集合的情况下可以优先使用Vector。

0x3. LinkedList

LinkedList采用的是链表结构存储数据，适合数据进行插入与删除的操作，效率高，而随机访问与遍历速度比较慢。除此之外，该类中还提供了别的List集合实现类中没有定义的方法，专门用于操作队头和队尾的元素，可以当作堆栈、队列和双向队列进行使用。

4. Set

实现Set集合接口的类主要有：HashSet，TreeSet，LinkedHashSet，Set中的值不可重复，该体系集合用于存储无序（存入与取出的顺序不一定相同）元素，值不可重复。

其保持值唯一的本质是通过对象的hashCode值（JVM根据对象的内存地址计算出来的序列号）进行判断的。

0x1. HashSet

HashSet表内部是一个HashMap，其底层实现还是hash值的方式，采用将输入的值保存在内部HashMap的Key中，从而达到除重的效果，而Value则由每次add时传入一个静态已初始化的object对象实现。

其add()方法源码效果如下所示：

private transient HashMap<E,Object> map;
// Dummy value to associate with an Object in the backing Map
private static final Object PRESENT = new Object();
public boolean add(E e) {
	return map.put(e, PRESENT)==null;
}

0x2. TreeSet

• TreeSet的排序机制利用的是二叉树的原理对新add()的对象按照指定的顺序排序（升序，降序），每增加一个对象都会进行排序，将对象插入二叉树指定的位置。
• Integer和String对象都可以进行默认的TreeSet排序，而自定义类的对象是不可以的，自定义的类必须实现Comparable接口，并且需要覆盖compareTo()函数，才能使用TreeSet集合进行排序。
• 在覆盖compare()函数时，还需要返回相应的值才能使得TreeSet按照一定的规则来排序。

0x3. LinkedHashSet

对于LinkedHashSet而言，它继承于HashSet、又基于LinkedHashMap实现，LinkedHashSet底层使用LinkedHashMap来保存所有元素，它继承于HashSet，其所有的方法操作与HashSet相同，因此LinkedHashSet的实现上非常简单，其只提供了4个构造方法，通过传递标识来调用父类的构造器 （即HashSet(int initialCapacity, float loadFactor, boolean dummy)） ，LinkedHashSet也是根据元素的hashcode值来决定元素的存储位置，但它使用链表维护元素的次序，因此元素的顺序和添加顺序一样，这就是LinkedHashSet与HashSet的区别。

因为LinkedHashSet需要通过额外的链表来维护元素的插入顺序，因此其性能比HashSet低。

5. Map

Map接口采用键值对Map的存储方式，保存具有映射关系的数据，因此，Map集合里保存两组值，一组值用于保存Map里的Key，另外一组值用于保存Map里的Value，Key和Value可以是任意引用类型的数据。Key值不允许重复，可以为null。如果添加Key-Value对Map中已经有重复的Key，则新添加的Value会覆盖该Key原来对应的Value。

常用实现类主要有HashMap、LinkedHashMap、TreeMap。

0x1. HashMap

HashMap是根据Key的hashcode值来存储相应的Value的，大多数情况下都能直接获取到该Key对应的值，因此具有很快的访问速度，但是其遍历顺序却是不确定的，HashMap最多只允许一条记录的键为null，允许多条记录的值为null。HashMap是线程不安全的，因此在同一时刻当有多条线程同时访问该HashMap时，可能会产生数据不一致的情况。如果需要满足线程安全，则可以使用Collections的synchronizedMap方法来使HashMap对象具有线程安全的能力，或者使用ConcurrentHashMap集合。

当HashMap中的元素个数超过数组大小 * loadFactor时，便会进行数组扩容，loadFactor负载因子的默认值是0.75，默认情况下，数组的大小为16，也就是在默认情况下，当数组大小达到了 16 * 0.75 = 12的时候，就会触发扩容机制，把容量扩大一倍，然后重新计算每个元素在数组中的位置，可以见得这是一件十分耗时的操作。因此，如果在使用HashMap前已经确定好大小，则可以通过构造函数传入初始值避免后续重复扩容，从而提高效率。

Java 7实现

其中，可以看见HashMap内部是一个数组，数组中的每个元素又是一个单向链表。图中，每个绿色的实体是嵌套类Entry的实例，Entry包中包含有四个属性，分别是key，value，hash与用于链表的next。

• capacity：当前数组容量，始终保持$2^n$，支持扩容，扩容后该数组大小为当前的2倍。
• loadFactor：负载因子，默认为0.75。
• threshold：扩容的阈值，等于capacity * loadFactor的值。

Java 8实现

Java 8中对HashMap进行了一些修改，最大的不同就是新增了红黑树，所以在Java 8中的HashMap是由数组 + 链表 + 红黑树构成的。

根据Java 7中的HashMap介绍，可知在查找时，可以根据hash值快速定位到所需要查找的元素，但当HashMap中存在大量相同的hash值的不同元素时，其数组坐标下的单链表中也将存在着大量不同的元素，而依据此单链表进行查找，效率显然慢了一些，需要顺着链表遍历才能获取到所需要查找的元素，时间复杂度也取决于该链表链表的长度——O(n)。为了提高该访问效率，在Java 8中，当相同hash值中链表的元素超过了8个以后，会将链表转换为红黑树，在这时，配合红黑树进行查找的效率将大幅提升，时间复杂度为——O(logN)。

0x2. LinkedHashMap

LinkedHashMap是HashMap的一个子类，使用了链表来保存记录的插入顺序，在使用Iterator迭代器进行遍历时，可以保证得到的记录是按插入顺序获取的，也可以在构造函数传入标记指明使用次序访问。同时因为使用链表进行记录插入顺序操作，所以在效率上差于HashMap。

0x3. TreeMap

TreeMap实现了SortedMap接口，能够把它保存的记录根据键排序，默认是按键值的升序排序，也可以指定排序的比较器，当使用Iterator迭代器进行遍历时，得到的记录是已经排序过的。

在使用TreeMap时，Key必须实现Comparable接口或者在构造TreeMap传入自定义的Comparator，否则会在运行时抛出java.lang.ClassCastException类型的异常。